package QuickSort;


import java.util.Arrays;

public class Quick {

    /*
    *       快速排序采用的是分治的思想。
    *       就是通过一趟排序将待排序的序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小
    *       然后分别的对这两部分的子序列继续进行排序操作最终达到序列有序
    */

    public static int partition(int[] array, int low, int high) {
        // 定义一个 基准 这里记录为 high 位置处的值
        // 这个 基准 会在之后发生变化
        int pivot = array[high];
        // 定义一个指针，记录当前传递过来数组的 最低位 元素
        int pointer = low;
        for (int i = low; i < high; i++) {
            // 通过对当前范围进行循环
            // 针对下面的规则进行判断
            if (array[i] <= pivot) {
                // 只要当前 i 位置的值和 high 位置的值不符合条件就进行一次交换
                swap(array,pointer,i);
                //  这里的指针记录的是只要发生一次交换操作就增加一次
                // 通过这样的形式找到分隔点
                pointer++;
            }
//            System.out.println(Arrays.toString(array));
        }
        // 将 基准值 和 最后值进行交换操作
        swap(array, pointer, high);
        return pointer;
    }
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 这里将相关信息传递到基准方法中寻找 基准
            int position = partition(array, low, high);
            // 向基准左侧进行排列
            quickSort(array, low, position - 1);
            // 向基准右侧进行排列
            quickSort(array, position + 1, high);
        }
    }

    public static void swap(int[] arr, int left, int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }


    public static void main(String[] args) {
        int[] arr = {9,8,7,5,4,6,3,2,1};
        quickSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
